import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author hewei
 * @version 1.0
 * @description: 2332. 坐上公交的最晚时间
 * @date 2022/10/27 15:34
 */

public class LatestTimeCatchTheBus {

    public static void main(String[] args) {
        int[] buses = {3};
        int[] passengers = {4};
        System.out.println(new LatestTimeCatchTheBus().latestTimeCatchTheBus(buses, passengers, 1));
    }

    public int latestTimeCatchTheBus1(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(buses);
        Arrays.sort(passengers);
        int n = buses.length;
        List<Integer>[] count = new List[n];
        int p = 0;
        for (int i = 0; i < buses.length; i++) {
            count[i] = new ArrayList<>();
            while (p < passengers.length && passengers[p] <= buses[i] && count[i].size() < capacity) {
                count[i].add(passengers[p++]);
            }
        }
        List<Integer> list = count[count.length - 1];
        if (list.size() < capacity && (list.size() == 0 || list.get(list.size() - 1) + 1 < buses[count.length - 1])) {
            return buses[count.length - 1];
        }
        for (int i = p - 1; i > 0; i--) {
            if (passengers[i] - passengers[i - 1] == 1) continue;
            return passengers[i] - 1;
        }
        return passengers[0] - 1;
    }

    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(buses);
        Arrays.sort(passengers);
        int n = buses.length, p = 0, delta = 0;
        for (int i = 0; i < n; i++) {
            for (int j = capacity; j > 0 && p < passengers.length && passengers[p] <= buses[i]; j--) {
                ++p;
                if (i == n - 1) delta++;
            }
        }
        p = p == 0 ? 0 : p - 1;
        if (delta != capacity && passengers[p] != buses[n - 1]) return buses[n - 1];
        for (int i = p; i > 0; i--) {
            if (passengers[i] - passengers[i - 1] == 1) continue;
            return passengers[i] - 1;
        }
        return passengers[0] - 1;
    }
}